/*************************************************************************
	> File Name: 001.HZOJ-47.0-1背包.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  6/28 22:05:02 2021
 ************************************************************************/

#include <iostream>
using namespace std;

int V, n, v[105], w[105], ans[105][1000005];

int main() {
    cin >> V >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < v[i]) { //放不下第i件物品
                ans[i][j] = ans[i - 1][j]; 
            } else {
                //可以放下第i件物品，在放与不放中选择价值大的
                ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << ans[n][V] << endl;

    return 0;
}
